package com.c2b.algorithm.leetcode.base;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 无重叠区间
 * <p>给定一个区间的集合intervals，其中 intervals[i] = [starti, endi]。返回 需要移除区间的最小数量，使剩余区间互不重叠。
 *
 * @author c2b
 * @since 2022/5/23 13:07
 */
public class LC0435eraseOverlapIntervals {

    /**
     * 贪心算法,以end1值从小到大排序
     *
     * @param intervals 区间的集合
     * @return int 需要移除区间的最小数量，使剩余区间互不重叠
     * @author c2b
     * @since  2022/5/23 13:07
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        int result = 0;
        // 使二维数组中的每个一维数组按照第二个元素按从小到大排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int prev = 0;
        int last = 1;
        while (last < intervals.length) {
            // 前一个数组的结束点,大于后一个数组的开始点,那么后一个数组需要移除
            if (intervals[prev][1] > intervals[last][0]) {
                ++result;
            } else {
                prev = last;
            }
            ++last;
        }
        return result;
    }
}